选择排序

选择排序就是把符合要求的数据选择出来进行排序

• 将序列分为有序部分和无序部分
• 第一次从待排序的数据元素选出最小(或最大)的一个元素
• 存放在序列的起始位置
• 再从剩余的未排序元素中寻找到最小(最大)元素
• 然后放到已排序的序列的末尾
• 以此类推，直到全部待排序的数据元素的个数为0

选择排序的工作过程

第一轮比较了4次，找到了最小值，进行了一次交换

第二轮比较了3次 进行了一次交换

代码实现

def select_sort(alist):
    """选择排序"""

    # 列表长度
    n = len(alist)

    # 控制比较轮数
    for j in range(0, n - 1):
        # 假定的最小值的下标, 默认为序列的第一个元素
        min_index = j
        # 控制比较次数
        for i in range(j + 1, n):
            # 进行比较，获得最小值
            if alist[i] < alist[min_index]:
                min_index = i

        # 如果假定的最小值下标发生了变化，那么我么那就进行交换
        if min_index != j:
            alist[j], alist[min_index] = alist[min_index], alist[j]

if __name__ == '__main__':
    alist = [1, 3, 4, 10, 0, 1000, 8]
    select_sort(alist)
    print(alist)

选择排序的稳定性

最差的时间复杂度$O(n^2)$，是一个不稳定的排序算法。